﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;

namespace UI.Dendrogram
{
    public class BinaryHierarchicalDataUtil
    {
        public static BinaryHierarchicalData BuildBinaryHierarchy(Dictionary<int,Dictionary<int,double>> distances)
        {
            List<BinaryHierarchicalData> allHierarchyData=new List<BinaryHierarchicalData>();

            Dictionary<double, List<string>> distanceIDPairs=
                new Dictionary<double, List<string>>();
            foreach(int fromID in distances.Keys)
            {
                foreach(int toID in distances[fromID].Keys)
                {
                    if(fromID==toID)
                        continue;
                    double distance = distances[fromID][toID];
                    string idPair = string.Format("{0}:{1}", fromID, toID);
                    if(fromID>toID)
                        idPair = string.Format("{0}:{1}", toID, fromID);
                    if (distanceIDPairs.ContainsKey(distance))
                    {
                        List<string> idPairs = distanceIDPairs[distance];
                        idPairs.Add(idPair);
                        distanceIDPairs[distance] = idPairs;
                    }
                    else
                    {
                        List<string> idPairs=new List<string>();
                        idPairs.Add(idPair);
                        distanceIDPairs.Add(distance,idPairs);
                    }
                }
            }
            List<double> uniqueDistances=new List<double>();
            uniqueDistances.AddRange(distanceIDPairs.Keys);
            uniqueDistances.Sort();
            foreach(double distance in uniqueDistances)
            {
                List<string> idPairs = distanceIDPairs[distance];
                foreach(string idPair in idPairs)
                {
                    string[] pair = idPair.Split(new char[] {':'});
                    int fromID = int.Parse(pair[0]);
                    int toID = int.Parse(pair[1]);
                    if(!ContainsLeaf(fromID,allHierarchyData) && !ContainsLeaf(toID, allHierarchyData))
                    {
                        int newID = GetNextTreeDataID(allHierarchyData);
                        BinaryHierarchicalData treeData =
                            new BinaryHierarchicalData(null, false, newID, "", distance, null);
                        new LeafData(treeData,true,fromID,"","");
                        new LeafData(treeData, false, toID, "", "");
                        allHierarchyData.Add(treeData);
                    }
                    else if(!ContainsLeaf(fromID,allHierarchyData))
                    {
                        BinaryHierarchicalData branchContainingLeaf =
                            GetRootBranchForLeaf(toID, allHierarchyData);
                        if(branchContainingLeaf!=null)
                        {
                            int newID = GetNextTreeDataID(allHierarchyData);
                            BinaryHierarchicalData treeData=
                                new BinaryHierarchicalData(null,false,newID,"", distance, null);
                            treeData.LeftChild = branchContainingLeaf;
                            new LeafData(treeData, false, fromID, "", "");
                            allHierarchyData.Add(treeData);
                        }
                    }
                    else if(!ContainsLeaf(toID, allHierarchyData))
                    {
                        BinaryHierarchicalData branchContainingLeaf =
                            GetRootBranchForLeaf(fromID, allHierarchyData);
                        if (branchContainingLeaf != null)
                        {
                            int newID = GetNextTreeDataID(allHierarchyData);
                            BinaryHierarchicalData treeData =
                                new BinaryHierarchicalData(null, false, newID, "", distance, null);
                            treeData.LeftChild = branchContainingLeaf;
                            new LeafData(treeData, false, toID, "", "");
                            allHierarchyData.Add(treeData);
                        }
                    }
                }
            }

            Dictionary<BinaryHierarchicalData, List<int>> rootBranchesWithLeaves =
                GetRootBranchWithLeaves(allHierarchyData);
            List<BinaryHierarchicalData> roots = new List<BinaryHierarchicalData>();
            roots.AddRange(rootBranchesWithLeaves.Keys);

            while (roots.Count > 1)
            {
                BinaryHierarchicalData leftRootBranch = null;
                BinaryHierarchicalData rightRootBranch = null;
                double minDistance = double.PositiveInfinity;
                for(int i=0;i<roots.Count;i++)
                {
                    BinaryHierarchicalData root1 = roots[i];
                    for(int k=i+1;k<roots.Count;k++)
                    {
                        BinaryHierarchicalData root2 = roots[k];
                        double distanceBetweenBranch = double.PositiveInfinity;
                        foreach(int fromID in rootBranchesWithLeaves[root1])
                        {
                            foreach(int toID in rootBranchesWithLeaves[root2])
                            {
                                if(distances.ContainsKey(fromID) && distances[fromID].ContainsKey(toID))
                                {
                                    if (distances[fromID][toID] < distanceBetweenBranch)
                                        distanceBetweenBranch = distances[fromID][toID];
                                }
                                if(distances.ContainsKey(toID) && distances[toID].ContainsKey(fromID))
                                {
                                    if (distances[toID][fromID] < distanceBetweenBranch)
                                        distanceBetweenBranch = distances[toID][fromID];
                                }
                            }
                        }
                        if(minDistance>distanceBetweenBranch)
                        {
                            minDistance = distanceBetweenBranch;
                            leftRootBranch = root1;
                            rightRootBranch = root2;
                        }
                    }
                }

                int newID = GetNextTreeDataID(allHierarchyData);
                BinaryHierarchicalData newRoot=
                    new BinaryHierarchicalData(null,false,newID,"",minDistance,null);
                newRoot.LeftChild = leftRootBranch;
                newRoot.RightChild = rightRootBranch;
                allHierarchyData.Add(newRoot);
                rootBranchesWithLeaves = GetRootBranchWithLeaves(allHierarchyData);
                roots = new List<BinaryHierarchicalData>();
                roots.AddRange(rootBranchesWithLeaves.Keys);
            }
            
            Debug.Assert(roots.Count == 1);
            return roots[0];
        }

        private static int GetNextTreeDataID(List<BinaryHierarchicalData> allTreeData)
        {
            int lastID = 0;
            foreach(BinaryHierarchicalData treeData in allTreeData)
            {
                if(treeData.ID>lastID)
                    lastID = treeData.ID;
            }
            return lastID + 1;
        }

        private static bool ContainsLeaf(int leafID, List<BinaryHierarchicalData> allTreeData)
        {
            foreach(BinaryHierarchicalData treeData in allTreeData)
            {
                if(treeData.LeftLeaf!=null && treeData.LeftLeaf.ID==leafID)
                    return true;
                else if(treeData.RightLeaf !=null && treeData.RightLeaf.ID==leafID)
                    return true;
            }
            return false;
        }

        public static BinaryHierarchicalData GetRootBranchForLeaf(int leafID, List<BinaryHierarchicalData> allTreeData)
        {
            BinaryHierarchicalData branchContainingLeaf = null;
            foreach(BinaryHierarchicalData treeData in allTreeData)
            {
                if(treeData.LeftLeaf !=null && treeData.LeftLeaf.ID==leafID)
                {
                    branchContainingLeaf = treeData;
                    break;
                }
                else if (treeData.RightLeaf!=null && treeData.RightLeaf.ID==leafID)
                {
                    branchContainingLeaf = treeData;
                    break;
                }
            }
            if(branchContainingLeaf !=null)
            {
                return GetRoot(branchContainingLeaf);
            }
            else
                return null;
        }

        private static Dictionary<BinaryHierarchicalData,List<int>> GetRootBranchWithLeaves(List<BinaryHierarchicalData> allTreeData)
        {
            Dictionary<BinaryHierarchicalData,List<int>> rootBranchWithLeaves=new Dictionary<BinaryHierarchicalData, List<int>>();
            foreach(BinaryHierarchicalData treeData in allTreeData)
            {
                BinaryHierarchicalData rootBranch = GetRoot(treeData);
                if(!rootBranchWithLeaves.ContainsKey(rootBranch))
                {
                    List<int> leafIDs = GetLeafIDsForBranch(rootBranch);
                    rootBranchWithLeaves.Add(rootBranch,leafIDs);
                }
            }
            return rootBranchWithLeaves;
        }

        private static BinaryHierarchicalData GetRoot(BinaryHierarchicalData treeData)
        {
            BinaryHierarchicalData parent = treeData;
            while(parent.Parent !=null)
                parent = parent.Parent;
            return parent;
        }

        public static List<int> GetLeafIDsForBranch(BinaryHierarchicalData treeData)
        {
            List<int> leafIDs=new List<int>();
            if(treeData.LeftLeaf !=null)
                leafIDs.Add(treeData.LeftLeaf.ID);
            if(treeData.RightLeaf !=null)
                leafIDs.Add(treeData.RightLeaf.ID);
            if(treeData.LeftChild!=null)
            {
                List<int> leafFromLeftChild = GetLeafIDsForBranch(treeData.LeftChild);
                leafIDs.AddRange(leafFromLeftChild);
            }
            if(treeData.RightChild !=null)
            {
                List<int> leafFromRightChild = GetLeafIDsForBranch(treeData.RightChild);
                leafIDs.AddRange(leafFromRightChild);
            }
            return leafIDs;
        }

        public static List<LeafData> GetLeavesForBranch(BinaryHierarchicalData treeData)
        {
            List<LeafData> leaves = new List<LeafData>();
            if (treeData.LeftLeaf != null)
                leaves.Add(treeData.LeftLeaf);
            if (treeData.RightLeaf != null)
                leaves.Add(treeData.RightLeaf);
            if (treeData.LeftChild != null)
            {
                List<LeafData> leafsFromLeftChild = GetLeavesForBranch(treeData.LeftChild);
                leaves.AddRange(leafsFromLeftChild);
            }
            if (treeData.RightChild != null)
            {
                List<LeafData> leafsFromRightChild = GetLeavesForBranch(treeData.RightChild);
                leaves.AddRange(leafsFromRightChild);
            }
            return leaves;
        }
    }
}
